#include "StdAfx.h"
#include <stdio.h>
#include <io.h>
#include <stdlib.h>
#include <direct.h>
#include <stdlib.h>
#include <stdio.h>

#include "lzss.h"


BOOL MkdirEx(const char* lpPath)
{
	CString pathname = lpPath;

	if(pathname.Right(1) != "\\")

		pathname += "\\" ;

	int end = pathname.ReverseFind('\\');

	int pt = pathname.Find("\\");

	if (pathname[pt-1] == ':')
		pt = pathname.Find("\\", pt+1);

	CString path;

	while(pt != -1 && pt<=end)
	{
		path = pathname.Left(pt+1);

		if(_access(path, 0) == -1)
			_mkdir(path);

		pt = pathname.Find("\\", pt+1);
	}
	return TRUE;
}


OutputBitStream::OutputBitStream(void)
{
	m_iStreamPosition = 0;
}

OutputBitStream::~OutputBitStream(void)
{
	m_byStreamArray.clear();
}

void OutputBitStream::OutputBit(int iBit)
{
	if ( iBit )
		m_iRack |= m_byMask;

    m_byMask = m_byMask >> 1;

    if ( m_byMask == 0 ) 
	{
		m_byStreamArray.push_back(m_iRack);

		m_iRack = 0;
		m_byMask= 0x80;//1000 0000
    }

}

void OutputBitStream::OutputBits(unsigned int dwCode,int iCount)
{
    unsigned int mask;

    mask = 1L << ( iCount - 1 );
    
	while ( mask != 0)
	{
		if ( mask & dwCode )
			m_iRack |= m_byMask;

		m_byMask = m_byMask >> 1;

		if ( m_byMask == 0 ) 
		{
			m_byStreamArray.push_back(m_iRack);

			m_iRack = 0;
			m_byMask= 0x80;
		}

        mask >>= 1;
    }
}

void OutputBitStream::CloseStream(void)
{
	if (m_byMask != 0x80 )
	{
		m_byStreamArray.push_back(m_iRack);
	}
}

void OutputBitStream::OpenStream(void)
{
	m_iRack = 0;
	m_byMask= 0x80;//1000 0000
}


InputBitStream::InputBitStream(void)
{
	m_pData = NULL;
}

InputBitStream::~InputBitStream(void)
{
	if (m_pData)
		delete [] m_pData;
}

BOOL InputBitStream::Create(FILE *fp,int iSize)
{
	m_iSize = iSize;

	m_pData = new unsigned char[m_iSize];

	fread(m_pData,m_iSize,1,fp);

    m_iRack  = 0;
    m_byMask = 0x80;
	m_iPosition = 0;

	return TRUE;
}

int InputBitStream::InputBit()
{
	int value;

    if ( m_byMask == 0x80 ) 
	{
        m_iRack = m_pData[m_iPosition++];
        
		if ( m_iPosition > m_iSize)
		{
            printf( "Fatal error in InputBit!\n" );
			ASSERT(0);
		}
	}

    value = m_iRack & m_byMask;
    m_byMask >>= 1;
    if ( m_byMask == 0 )
	{
		m_byMask = 0x80;
	}

    return  (value) ? 1 : 0 ;
}

unsigned int InputBitStream::InputBits(int iCount)
{
	unsigned int mask;
	unsigned int return_value;

	mask = 1L << ( iCount - 1 );
	return_value = 0;
	
	while ( mask != 0)
	{
		if ( m_byMask == 0x80 ) 
		{
			m_iRack = m_pData[m_iPosition++];
			if ( m_iPosition > m_iSize)
			{
				printf( "Fatal error in InputBit!\n" );
				ASSERT(0);
			}
		}

		if ( m_iRack & m_byMask )
		{
			return_value |= mask;
		}

		mask >>= 1;
		m_byMask >>= 1;
		if ( m_byMask == 0 )
		{
			m_byMask = 0x80;
		}
	}
	return( return_value );
}

lzss::lzss(void)
{
}

lzss::~lzss(void)
{
}

void lzss::InitTree(int r)
{
	ZeroMemory(tree,(WINDOW_SIZE + 1) * sizeof(tagTree));

	tree[TREE_ROOT].larger_child = r;
	tree[r].parent = TREE_ROOT;
	tree[r].larger_child = LZSSUNUSED;
	tree[r].smaller_child = LZSSUNUSED;
}

void lzss::ContractNode(int old_node,int new_node)
{
	tree[new_node].parent = tree[old_node].parent;
	if (tree[tree[old_node].parent].larger_child == old_node)
		tree[tree[old_node].parent].larger_child = new_node;
	else
		tree[tree[old_node].parent].smaller_child = new_node;

	tree[old_node].parent = LZSSUNUSED;
 }

void lzss::ReplaceNode(int old_node,int new_node)
{
	int parent;
	parent = tree[old_node].parent;
	if (tree[parent].smaller_child == old_node)
		tree[parent].smaller_child = new_node;
	else
		tree[parent].larger_child = new_node;
	tree[new_node] = tree[old_node];
	tree[tree[new_node].smaller_child].parent = new_node;
	tree[tree[new_node].larger_child].parent = new_node;
	tree[old_node].parent = LZSSUNUSED;
}

int lzss::FindNextNode(int node)
{
	int next;
	next = tree[node].smaller_child;
	while(tree[next].larger_child != LZSSUNUSED)
		next = tree[next].larger_child;
	return (next);
}

void lzss::DeleteString(int p)
{
	int replacement;

	if (tree[p].parent == LZSSUNUSED)
		return;
	if (tree[p].larger_child == LZSSUNUSED)
		ContractNode(p,tree[p].smaller_child);
	else if (tree[p].smaller_child == LZSSUNUSED)
		ContractNode(p,tree[p].larger_child);
	else
	{
		replacement = FindNextNode(p);
		DeleteString(replacement);
		ReplaceNode(p,replacement);
	}
}

int lzss::AddString(int new_node,int * match_position)
{
	int i;
	int test_node;
	int delta;
	int match_length;
	int * child;

	if (new_node == END_OF_STREAM)
		return 0;
	test_node = tree[TREE_ROOT].larger_child;
	match_length = 0;
	for(;;)
	{
		for(i  =0 ; i < LOOK_AHEAD_SIZE;i++)
		{
			delta = window[MOD_WINDOW(new_node+i)]- window[MOD_WINDOW(test_node + i)];
			if (delta != 0)
				break;
		}
	
		if (i  >= match_length)
		{
			match_length = i;
			*match_position = test_node;
			if (match_length >= LOOK_AHEAD_SIZE)
			{
				ReplaceNode(test_node,new_node);
				return match_length;
			}
		}

		if (delta>=0)
			child = &tree[test_node].larger_child;
		else
			child = &tree[test_node].smaller_child;

		if ( *child == LZSSUNUSED)
		{
				*child = new_node;
				tree[new_node].parent = test_node;
				tree[new_node].larger_child = LZSSUNUSED;
				tree[new_node].smaller_child = LZSSUNUSED;
				return match_length;
		}
		test_node = *child;
	}
}




BOOL lzss::Decode(const char *szFileName,std::vector<BYTE> *output)
{
	output->clear();


	FILE *fp = fopen(szFileName,"rb");
	if (!fp)
	{
		return FALSE;
	}

	fseek(fp,0,SEEK_END);
	int iSize = ftell(fp);
	fseek(fp,4,SEEK_SET);

	InputBitStream input;
	
	if (!input.Create(fp,iSize - 4))
	{
		return FALSE;
	}

	fclose(fp);

	int i,current_position;
	int c;
	int match_length;
	int match_position;

	current_position = 1;
	for(;;)
	{
		if (input.InputBit())
		{
			c = (int)input.InputBits(8);
			output->push_back((BYTE)c);
			window[current_position] = (BYTE)c;
			current_position = MOD_WINDOW(current_position + 1);
		}
		else
		{
			match_position = (int)input.InputBits(INDEX_BIT_COUNT);
			if (match_position == END_OF_STREAM)
				break;
			match_length = (int)input.InputBits(LENGTH_BIT_COUNT);
			match_length +=BREAK_EVEN;
			for(i = 0; i <= match_length;i++)
			{
				c = window[MOD_WINDOW(match_position + i)];
				output->push_back((BYTE)c);
				window[current_position] = (BYTE)c;
				current_position = MOD_WINDOW(current_position + 1);
			}
		}
	}
	return TRUE;
}